# -*- coding:utf-8
# 5172. 形成三的最大倍数 显示英文描述
# 用户通过次数461
# 用户尝试次数798
# 通过次数482
# 提交次数2051
# 题目难度Hard
# 给你一个整数数组 digits，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。
# 输入：digits = [8, 1, 9]
# 输出："981"
#
# 由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。
#
# 如果无法得到答案，请返回一个空字符串。

# Dp做复杂了，dp ij代表的意义就是遍历到i余数为j的最大值，状态转移时要么从上个状态直接复制过来，要么加上新的一位数字，然后再考虑余数的情况


from typing import  List
class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        if sum(digits) %3 == 0:

            res = sorted(digits,reverse=True)
            if res[0] == 0 :
                return "0"
            else:

                strLis= [str(num) for num in res]
                return "".join(strLis)

        sortedDigits = sorted(digits,reverse=True)
        lennn = len(digits)
        popIdx = -1
        popIdx0 = -1
        popIdx1 = -1
        if sum(digits) %3 == 1:
            ##寻找1,4,7
            for idx in range(lennn-1,-1,-1):
                if popIdx == -1 and (sortedDigits[idx] == 1 or sortedDigits[idx] == 4 or sortedDigits[idx] == 7):
                    popIdx = idx
                if popIdx0 == -1 and (sortedDigits[idx] == 2 or  sortedDigits[idx] == 5 or sortedDigits[idx] == 8):
                    popIdx0 = idx
                elif popIdx0 != -1 and popIdx1 == -1 and (sortedDigits[idx] == 2 or  sortedDigits[idx] == 5 or sortedDigits[idx] == 8):
                    popIdx1 = idx


            if popIdx != -1:
                sortedDigits.pop(popIdx)
                if sortedDigits.__len__()>0:
                    strLis = [str(num) for num in sortedDigits]
                    return "".join(strLis)
                else:
                    return ""
            else:
                if popIdx0>=0 and popIdx1>=0:
                    print("p1p0:",popIdx1,popIdx0)
                    sortedDigits.pop(popIdx0)
                    sortedDigits.pop(popIdx1)
                if sortedDigits.__len__()>0:
                    strLis = [str(num) for num in sortedDigits]
                    return "".join(strLis)
                else:
                    return ""





        elif sum(digits) %3 == 2:
            ##寻找2,5,8
            for idx in range(lennn - 1, -1, -1):
                if popIdx == -1 and (sortedDigits[idx] == 2 or sortedDigits[idx] == 5 or sortedDigits[idx] == 8):
                    popIdx = idx
                if popIdx0 == -1 and (sortedDigits[idx] == 1 or sortedDigits[idx] == 4 or sortedDigits[idx] == 7):
                    popIdx0 = idx
                elif popIdx0 != -1 and popIdx1 == -1 and (
                            sortedDigits[idx] == 1 or sortedDigits[idx] == 4 or sortedDigits[idx] == 7):
                    popIdx1 = idx

            if popIdx != -1:
                sortedDigits.pop(popIdx)
                if sortedDigits.__len__() > 0:
                    strLis = [str(num) for num in sortedDigits]
                    return "".join(strLis)
                else:
                    return ""
            else:
                if popIdx0 >= 0 and popIdx1 >= 0:
                    sortedDigits.pop(popIdx0)
                    sortedDigits.pop(popIdx1)
                if sortedDigits.__len__() > 0:
                    strLis = [str(num) for num in sortedDigits]
                    return "".join(strLis)
                else:
                    return ""
        return "qwer"

res = Solution().largestMultipleOfThree([7,8,7,2,1,2,6,6,9,2])
print(res)



